Thoughts on Concatenative Readability

Concatenative style programming languages are, indeed, powerful and concise. However, they are generally consider to be “read only” languages. The LISP family of languages (including Clojure) shares this same fate, and for much the same reason. The lack of boilerplate verbiage grants power, but hinders readability. Since programmers spend far more time reading code than writing it, this is not a good thing.

The Problem

Compare and contrast the following single line forms:

Concatenative:  
    3 2 > {“3 > 2 is true”} {“3 > 2 is false”} if println

Clojure:  
    (println (if (> 3 2) “3 > 2 is true” “3 > 2 is false”))

Python:  
    print(“3 > 2 is true” if 3 > 2 else “3 > 2 is false”)

Which one is the easiest to read? Now realize that the one-liner isn’t the easiest form of a Python if statement. Let’s split them up across multiple lines and make them as clear as possible.

Concatenative:
    3 2 >
        {“3 > 2 is true” println} 
        {“3 > 2 is false” println} 
    if

Clojure:
    (if (> 3 2) 
        (println “3 > 2 is true” )
        (println “3 > 2 is false”)
    )

Python:
    if 3 > 2:
        print(“3 > 2 is true”)
    else:
        print(“3 > 2 is false”)

The Solution

There are a pair of simple constructs that can make a concatenative language much easier to read. These are the single-word comment and the function-call syntax.

Let’s start with this. It’s not terrible, but could obviously be better.

    3 2 > "3 > 2 is true" "3 > 2 is false" if println

We can visually pick out the conditional in a block. Remember, (blocks) are immediately unpacked for evaluation. {Quotes} and [data] are not. Lines and indentation help, as well.

    (3 2 >) 
        {“3 > 2 is true”} 
        {“3 > 2 is false”} 
    if 
    println

Single word comments: The commenting word is attached to double backslashes. No space between them is allowed, or else it becomes a comment to the end of the line.

\\if (3 2 >)
    \\then {“3 > 2 is true” println} 
    \\else {“3 > 2 is false” println} 
if

Function-call syntax: This is a parser hack. It takes the instruction attached to the front of a block (and only a block) and moves it to the last position inside the block. For example, the following all evaluate to 3.

    1 2 +
    1 (2 +)
    (1) (2 +)
    (1) (2) (+)
    +(1 2)
    1 +(2)
    (1) +(2)
    (1)+(2)

Getting back to our sample program, we can now write it like this:

    if(>(3 2) “3 > 2 is true” “3 > 2 is false”) println
becomes:
    ((3 2 >) "3 > 2 is true" "3 > 2 is false" if) println

Even better, mix these two special forms together for maximum clarity, along with separate lines and indentation. A little code duplication can also help ease readability.

    if( 3 >(2)  \\ This becomes 3 (2 >) which gets evaluated as 3 2 >
        \\then {"3 > 2 is true" println}
        \\else {"3 > 2 is false" println}
    )

There are many occasions when you need to do some complicated computation to base your branching code on. Or the branch might occur based on some factor you don’t know ahead of time, like user input or a database read. That’s fine. Just rewrite your program using the function-call form and indentation to your advantage.

    print("Enter a number: ")
    getNum
    (dup * 100 >) 
        if(
            \\then "The square of your number is greater than 100." 
            \\else "The square of your number is not greater than 100."
        )
    println
    

Partial Application

The last program looks an awful lot like partial application. That’s because it is. Partial application is trivial in a concatenative language. It’s how all the functions work, because they expect to have their arguments waiting for them on the stack.

We can define an increment function like so:

    define(
        {1 +}
        \\as "inc"
    )

    2 inc \\ --> 2 (1 +) --> 3

Want to make a custom adder? That’s only a bit more complicated.

    2  
    {+} curry "addTwo" define

    1 addTwo \\ --> 1 (2 +) --> 3

Want to make a custom adder generator? That requires just a bit more thought.

    \\ expects: #number "name"
    define(
        { { {+} curry} dip  
            \\ the stack is now: {#number +} "name"
            define
        } 
        \\as "adderGenerator"
    )

    3 "addThree" adderGenerator
    1 addTwo addThree \\ --> 1 (2 +) (3 +) --> 6
    "addSix" adderGenerator  \\ 6 is already on top of the stack
    4 addSix \\ --> 4 (6 +) --> 10

    \\[ Without the comments and formatting, this function-defining function definition is just:
            { { {+} curry} dip define} "adderGenerator" define
    \\]

Try doing that in most other language styles.

Multiple Asides

• The writing of functions without variables is called point free programming.

• Functional composition is sometimes referred to as railway or pipeline oriented programming.

• In concatenative programming, it’s easy to associate data with code using quotes and combinators. Language-level closures are largely unnecessary.

A Symbology for Concatenative Combinators

I believe that one of the problems with the study of concatenative combinators is a fundamental misunderstanding of the symbology used to represent them. (Most of the explanations I have seen skip steps, or conflate the function being executed with the data on the top of the stack.) The theory is simple enough. After all, it is essentially an order-reversed version of the Lambda Calculus implemented on a Turing Machine style tape, effectively implementing the Church-Turing thesis. Now that I’ve thoroughly confused you, let’s get on with it.

Definitions and Terminology

The present: The current instruction being executed. Data is a very simple form of instruction. (2 is a function that pushes the number 2 onto the stack.) Represented as an instruction placed inside a pair of vertical bars:
|X|

The future: Instructions waiting to be executed. This is better known as the command queue. Represented as everything to the right of the present bars, with the leftmost as the next instruction to be executed:
|| X Y Z

The past: Data derived from the previous execution of instructions. This is better known as the data stack. Represented as everything placed to the left of the present bars, with the newest on top:
a b c ||

Comments are denoted by a double backslash.
\\SingleWordComment
\\ Comment to the end of the line. Notice the space after the backslashes.
\\[Multiline
comment \\]
\\[Comment followed by \\] instructions and data

Basic Procedure

Instructions are devoured from the future, executed in the present, and produce data that gets appended to the past. This act of executing an instruction or otherwise advancing through the program’s execution is depicted as the forward arrow → of time. Instructions follow the data they act upon. (This is known as postfix or reverse Polish notation.)

|| a b c X Y Z → |a| b c X Y Z → a || b c X Y Z → a |b| c X Y Z → a b || c X Y Z

In this summary, simple data elements are written as numbers or lower case variables. Instructions are written as upper case variables, or actual names. Blocks (unpacked and executed immediately) are represented with parenthesis (X Y Z). Quoted blocks, or quotes (treated as data until unquoted), are represented with curly braces {X Y Z}. Lists of data are represented as square brackets [a b c].

|| [a b] c → |[a b]| c → [a b] || c
|| {X Y} Z → |{X Y}| Z → {X Y} || Z
|| (X Y) Z → |(X Y)| Z → || X Y Z

A single backslash represents a temporary quote, or pass. It passes the instruction to its right directly to the stack without executing it. The future is transferred to the past without passing through the present. The pass character may be prepended to the instruction for clarity and succinctness.

a b c || \ X Y Z → a b c |\| X Y → a b c X || Y
a b c || \X Y Z → a b c |\X| Y → a b c X || Y
a b c || \( X Y) Z → a b c |\(X Y)| Z → a b c (X Y) || Z

Simple Instructions

|| 1 2 + → |1| 2 + → 1 || 2 + → 1 |2| + → 1 2 || + → 1 2 |+| → 3 ||
1 2 |-| → -1 ||
1 2 |*| → 2 ||
1 2 |/| → 0.5 ||
5 3 |div| → 1 || \\ Integer division.
5 3 |mod| → 2 || \\ Modulo arithmetic = remainder after integer division.
5 3 |divMod| → 1 2 || \\ A function can produce multiple return values.
1 2 |dup| → 1 2 2 ||
1 2 |drop| → 1 ||

Predicates are functions that return a Boolean value (true or false).
2 1 |>| → true ||
1 2 |>| → false ||
3 |odd?| → true ||
3 |even?| → false ||

Eval

You can now understand what the eval command does. It takes the top element of the stack and moves it to the present for execution.

(X Y Z) |eval| → |(X Y Z)| → || X Y Z
{X Y Z} |eval| → |{X Y Z}| → {X Y Z} ||
[a b c] |eval| → |[a b c]| → [a b c] ||
a b c |eval| → a b |c| → a b c ||
1 2 + |eval| → 1 2 |+| → 3 ||

The dup (duplicate) command duplicates the top element of the data stack without evaluating it.

a b |dup| → a b b ||

So, to summarize what we have so far, here is a very simple program.

|| a \dup eval → |a| \dup eval → a || \dup eval → a |\dup| eval → a dup || eval →
a dup |eval| → a |dup| → a a ||

Part of the simple genius of concatenative programming is that a long series of predictable steps can be replaced by what they eventually produce.

a \dup eval => a a

As is probably obvious, a passed command followed immediately by eval reduces to just the bare command.

\X eval => X

Do

do is a more powerful form of eval.
{X Y Z} |do| → || X Y Z
(X Y Z) |do| → || X Y Z
[1 2 3] |do| → [1 2 3] ||

do dereferences variables in lists. eval does not.
\\ Where a=1, b=2, c=3.
[a b c] |eval| → [a b c] ||
[a b c] |do| → [1 2 3] ||

do evaluates each element in a list as an instruction, then enlists the results.
[a 1 + b 2 * c dup] |do| → → [2 4 3 3] ||

Combinators

A combinator is simply an instruction that acts on other instructions or quotes. This normally happens through rearranging, quoting, or unquoting.

Here are some of the more common combinators. The actual commands vary a bit from language to language, but these will give you the sense of them.

a b |dup| → b b ||
a b |drop| → a ||
a b |quote| → a {b} ||
a {b c} |dequote| → a b c ||
a b |nip| → b ||
a b |swap| → b a ||
a b |over| → a b a ||
a b c |rotl| → b c a ||
a b c |rotr| → c a b ||
a b |dupd| → a a b ||
a b c |swapd| → b a c ||
{a} b |append| → {a b} ||
{a} b |prepend| → {b a} ||
{a} {b} |concat| → {a b} ||
a {b} |curry| → {a b} || \\ Named for Haskell Curry, who developed combinators.
{a} {b} |curry| → {{a} b} || \\ Some languages use cons for this.

Now we get into some of the more advanced combinators. These start moving things from the past to the future. They’re incredibly handy. (Functional bros call these higher order functions.)

a b X |dip| → a || X \b \\ Data moved to the future is passified.
a b {X Y} |dip| → a || X Y \b \\ Function quotes are unpacked.
a b X |keep| → a b || X \b
a b {X Y} |keep| → a b || X Y \b \\ This is the last quote I’m going to explicitly show.
a b X Y |doBoth| → a || X \b Y \\ Spreads two functions across two data.
a b X |doToBoth| → a || X \b X \\ Applies one function to two data.
a X Y |doBothTo| → a || X \a Y \\ Applies two functions to one data.

There are a whole series of combinators that act on lists of data, generally producing lists of data. They’re just different common iterators.

[1 2 3] {2 *} |map| → [2 4 6] || \\ Apply a function to each element.
[2 3 4] 0 {+} |reduce| → 9 || \\ Apply a function to each element in turn, from a baseline.
[2 3 4] 1 {*} |reduce| → 24 ||
[2 3 4] 0 {*} |reduce| → 0 ||
[1 2 3] 0 {+} |mapReduce| → [1 3 6] || \\ Produces a running total.
[1 2 3 4 5 6] {odd?} |filter| → [1 3 5] || \\ Requires a predicate.
[1 2 3 4 5 6] {3 >} |filter| → [4 5 6] ||

Control Flow

Control flow in concatenative languages is accomplished by, you guessed it, combinators. For example, the if combinator takes three arguments: a predicate and two functions (or quotes). If the predicate resolves as true, if evaluates the first function, otherwise the second.

3 || (2 >) {“greater than 2”} {“less than 2”} if → || “greater than 2”

The while combinator takes a predicate and a function. It repeatedly evaluates the function as long as the predicate returns true.

10 || {dup 0 >} {dup print “ …” println 1 -} while “Liftoff!” println

Notice that we could take everything in the future part of the above, and create a new instruction from it.

{ {dup 0 >} {dup print “ …” println 1 -} while “Liftoff!” println } “countdown” define

Now we can use countdown with any starting value we want.

20 countdown

---

I hope this summary helped clarify the topic. There are a lot more details to explore, but this should have provided a solid foundation. Remember, the vertical bars || surrounding the present instruction are a notational tool for understanding. They don’t actually appear in any program.

Something modern concatenative style programming sneaks in almost for free: anonymous functions. (Functional bros call them lambdas.) They’re just quotes. Pass them around like any other piece of data, because that’s all they are.

Reference 1: The Theory of Concatenative Combinators, Brent Kirby, 2002
Reference 2: The Mathematical Foundations of Joy, Manfred Von Thun, 2001